package LeetcodeTest_fifteen;
//对称二叉树

import java.util.*;
public class isSymmetric
{
    public static void main(String[] args)
    {
        TreeNode root = null;
        root = Solutions.createTree(root);
        System.out.println(Solutions.isSymmetric(root));
    }
}
class Solutions
{
    public static boolean isSymmetric(TreeNode root)
    {
        if(root==null)
            return true;
        ArrayList<String> result=new ArrayList<String>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();//将节点存到队列
        int curr,next,x;
        curr=x=1;//当前层的节点数量
        next=0;//下一层的节点数量
        queue.offer(root);
        while(!queue.isEmpty())
        {
            TreeNode tree=queue.poll();
            if(tree!=null)
                result.add(tree.val+"");
            else
                result.add("null");
            curr--;
            if(tree!=null)
            {
                if (tree.left != null)
                {
                    queue.offer(tree.left);
                    next++;
                }
                else
                {
                    queue.offer(null);
                    next++;
                }
                if (tree.right != null)
                {
                    queue.offer(tree.right);
                    next++;
                }
                else
                {
                    queue.offer(null);
                    next++;
                }
            }
            if(curr==0)
            {
                List<String> layer=new ArrayList<String>();
                for(int i=result.size()-x;i<result.size();i++)
                    layer.add(result.get(i));
                for(int i=0;i<=(layer.size()-1)/2;i++)
                {
                    if(!layer.get(i).equals(layer.get(layer.size()-1-i)))
                        return false;
                }
                curr=next;
                x=curr;
                next=0;
            }
        }
        return true;
    }
    public static TreeNode createTree(TreeNode T)
    {
        Scanner reader=new Scanner(System.in);
        int a=reader.nextInt();
        TreeNode p=null;
        if (a==-1)
            p=null;
        else
            p = new TreeNode(a);
        T=p;
        if(T==null)
            return T;
        else
        {
            T.left = createTree(T.left);
            T.right = createTree(T.right);
        }
        return T;
    }
}
